package summary;

import java.util.Arrays;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class Title106 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return null;
        }
        //1、后序遍历最后一个节点作为根节点
        int rootValue = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootValue);
        if (postorder.length == 1) {
            return root;
        }
        //2、判断根在inorder中的位置
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (rootValue == inorder[i]) {
                rootIndex = i;
                break;
            }
        }
        //3、左[0, rootIndex) 右[rootIndex+1, length-1)
        int[] inorderLeft = Arrays.copyOfRange(inorder, 0, rootIndex);
        int[] inorderRight = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);
        int[] postorderLeft = Arrays.copyOfRange(postorder, 0, rootIndex);
        int[] postorderRight = Arrays.copyOfRange(postorder, rootIndex, postorder.length - 1);
        root.left = buildTree(inorderLeft, postorderLeft);
        root.right = buildTree(inorderRight, postorderRight);
        return root;
    }

    public static TreeNode buildTree1(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        return traversal(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    public static TreeNode traversal(int[] inorder, int inorderBegin, int inorderEnd, int[] postorder, int postorderBegin, int postorderEnd) {
        if (postorderEnd - postorderBegin == 0) {
            return null;
        }
        int rootValue = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootValue);
        if (postorderEnd - postorderBegin == 1) {
            return root;
        }
        //1、从inorder数组确定根节点位置
        int rootIndex;
        for (rootIndex = inorderBegin; rootIndex < inorderEnd; rootIndex++) {
            if (inorder[rootIndex] == rootValue) {
                break;
            }
        }
        //2、分割inorder数组
        int inorderLeftBegin = inorderBegin;
        int inorderLeftEnd = rootIndex;
        int inoderRightBegin = rootIndex + 1;
        int inoderRightEnd = inorderEnd;
        //3、分割postorder数组
        int postorderLeftBegin = postorderBegin;
        int postorderLeftEnd = postorderBegin + (rootIndex - inorderLeftBegin);
        int postorderRightBegin = postorderLeftEnd;
        int postorderRightEnd = postorderEnd - 1;
        root.left = traversal(inorder, inorderLeftBegin, inorderLeftEnd, postorder, postorderLeftBegin, postorderLeftEnd);
        root.right = traversal(inorder, inoderRightBegin, inoderRightEnd, postorder, postorderRightBegin, postorderRightEnd);
        return root;
    }






    public TreeNode buildTree3(int[] inorder, int[] postorder) {
        return backTracking(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode backTracking(int[] inorder, int inorderStart, int inorderEnd,
                                  int[] postorder, int postorderStart, int postorderEnd) {
        //子树为空
        if (inorderStart == inorderEnd) {
            return null;
        }
        //确定根的值
        int rootValue = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootValue);
        //确定根在先序队列中的位置
        int rootIndex;
        for (rootIndex = inorderStart; rootIndex < inorderEnd; rootIndex++) {
            if (rootValue == inorder[rootIndex]) {
                break;
            }
        }
        //构建树  先序左+中序左   先序右+中序右
        int inorder_left_start = inorderStart;
        int inorder_left_end = rootIndex;
        int inorder_right_start = rootIndex + 1;
        int inorder_right_end = inorderEnd;

        int postorder_left_start = postorderStart;
        int postorder_left_end = postorderStart + (rootIndex - inorderStart);
        int postorder_right_start = postorder_left_end;
        int postorder_right_end = postorderEnd - 1;
        root.left = backTracking(inorder, inorder_left_start, inorder_left_end,
                postorder, postorder_left_start, postorder_left_end);
        root.right = backTracking(inorder, inorder_right_start, inorder_right_end,
                postorder, postorder_right_start, postorder_right_end);
        return root;
    }

    public static void main(String[] args) {
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        buildTree1(inorder, postorder);
    }
}
